package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envType=study-plan-v2&envId=top-interview-150">寻找两个正序数组的中位数(Median of Two Sorted Arrays)</a>
 * <p>给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。</p>
 * <p>算法的时间复杂度应该为 O(log (m+n)) 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums1 = [1,3], nums2 = [2]
 *      输出：2.00000
 *      解释：合并数组 = [1,2,3] ，中位数 2
 *
 * 示例 2：
 *      输入：nums1 = [1,2], nums2 = [3,4]
 *      输出：2.50000
 *      解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>nums1.length == m，nums2.length == n</li>
 *      <li>0 <= m，n<= 1000</li>
 *      <li>-10^6 <= nums1[i], nums2[i] <= 10^6</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/20 15:02
 */
public class LC0004MedianOfTwoSortedArrays_H {

    static class Solution {

        /**
         * <p>
         * 用 len 表示合并后数组的长度，如果是奇数，我们需要知道第 （len+1）/2 个数就可以了，如果遍历的话需要遍历 int(len/2 ) + 1 次。如果是偶数，我们需要知道第 len/2和 len/2+1 个数，也是需要遍历 len/2+1 次。所以遍历的话，奇数和偶数都是 len/2+1 次。
         * </p>
         * <p>
         * 返回中位数的话，奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量 left 和 right，right 保存当前循环的结果，在每次循环前将 right 的值赋给 left。这样在最后一次循环的时候，left 将得到 right 的值，也就是上一次循环的结果，接下来 right 更新为最后一次的结果。
         * </p>
         * <p>
         * 循环中该怎么写，什么时候 A 数组后移，什么时候 B 数组后移。用 aStart 和 bStart 分别表示当前指向 A 数组和 B 数组的位置。如果 aStart 还没有到最后并且此时 A 位置的数字小于 B 位置的数组，那么就可以后移了。也就是aStart＜m&&A[aStart]< B[bStart]。
         * </p>
         * <p>
         * 但如果 B 数组此刻已经没有数字了，继续取数字 B[ bStart ]，则会越界，所以判断下 bStart 是否大于数组长度了，这样 || 后边的就不会执行了，也就不会导致错误了，所以增加为 aStart＜m&&(bStart) >= n||A[aStart]<B[bStart]) 。
         * </p>
         */
        public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
            int num1Len = nums1.length;
            int num2Len = nums2.length;
            int totalLen = num1Len + num2Len;
            if (num1Len == 0) {
                return num2Len % 2 == 0 ? (nums2[totalLen >> 1] + nums2[(totalLen >> 1) - 1]) / 2.0 : nums2[totalLen >> 1];
            }
            if (num2Len == 0) {
                return num1Len % 2 == 0 ? (nums1[totalLen >> 1] + nums1[(totalLen >> 1) - 1]) / 2.0 : nums1[totalLen >> 1];
            }
            int num1Index = 0;
            int num2Index = 0;
            int currIndexVal = -1;
            int prevIndexVal = -1;
            int currIndex = 0;
            while (currIndex <= (totalLen >> 1)) {
                prevIndexVal = currIndexVal;
                if (num1Index < num1Len && num2Index < num2Len) {
                    if (nums1[num1Index] < nums2[num2Index]) {
                        currIndexVal = nums1[num1Index];
                        num1Index++;
                    } else {
                        currIndexVal = nums2[num2Index];
                        num2Index++;
                    }
                } else if (num1Index < num1Len) {
                    currIndexVal = nums1[num1Index];
                    num1Index++;
                } else {
                    currIndexVal = nums2[num2Index];
                    num2Index++;
                }
                currIndex++;
            }
            //return totalLen % 2 == 0 ? (currIndexVal + prevIndexVal) / 2.0 : currIndexVal;
            return (totalLen & 1) == 0 ? (currIndexVal + prevIndexVal) / 2.0 : currIndexVal;
        }

        /**
         * 先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。再根据奇数，还是偶数返回中位数。
         * <ul>
         *     <li>时间复杂度：O(m+n)</li>
         *     <li>空间复杂的：O(1)</li>
         * </ul>
         */
        public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
            int num1Len = nums1.length;
            int num2Len = nums2.length;
            int totalLen = num1Len + num2Len;
            if (num1Len == 0) {
                return num2Len % 2 == 0 ? (nums2[totalLen >> 1] + nums2[(totalLen >> 1) - 1]) / 2.0 : nums2[totalLen >> 1];
            }
            if (num2Len == 0) {
                return num1Len % 2 == 0 ? (nums1[totalLen >> 1] + nums1[(totalLen >> 1) - 1]) / 2.0 : nums1[totalLen >> 1];
            }
            int num1Index = 0;
            int num2Index = 0;
            int[] ints = new int[totalLen];
            int currIndex = 0;
            while (num1Index < num1Len && num2Index < num2Len) {
                if (nums1[num1Index] < nums2[num2Index]) {
                    ints[currIndex++] = nums1[num1Index++];
                } else {
                    ints[currIndex++] = nums2[num2Index++];
                }
            }
            // nums1走完了
            if (num1Index == num1Len) {
                while (num2Index < num2Len) {
                    ints[currIndex++] = nums2[num2Index++];
                }
            }
            // nums2走完了
            if (num2Index == num2Len) {
                while (num1Index < num1Len) {
                    ints[currIndex++] = nums1[num1Index++];
                }
            }
            return totalLen % 2 == 0 ? (ints[(totalLen >> 1) - 1] + ints[totalLen >> 1]) / 2.0 : ints[totalLen >> 1];
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findMedianSortedArrays2(new int[]{1, 2}, new int[]{3, 4}));
    }
}
